//
// Created by 刘振舟 on 2024/3/18.
//
#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>

struct ListNode {
    int val;
    struct ListNode *next;
};


void test()  {
    printf("hello world!");
}

struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2) {
    struct ListNode* dummy = (struct ListNode *) malloc(sizeof(struct ListNode)), *p = dummy;
    dummy->next = NULL;
    struct ListNode* p1 = list1, *p2 = list2;
    while (p1 && p2) {
        if (p1->val > p2->val) {
            p->next = p2;
            p2 = p2->next;
        } else {
            p->next = p1;
            p1 = p1->next;
        }
        p = p->next;
    }
    if (p1) {
        p->next = p1;
    }
    if (p2) {
        p->next = p2;
    }
    return dummy->next;
}

struct ListNode* partition(struct ListNode* head, int x){
    struct ListNode* dummy1 = (struct ListNode*) malloc(sizeof (struct ListNode));
    struct ListNode* dummy2 = (struct ListNode*) malloc(sizeof (struct ListNode));
    dummy2->next = NULL;

    struct ListNode* p = head;
    struct ListNode* p1 = dummy1, *p2 = dummy2;

    while (p) {
        if (p->val < x) {
            p1->next = p;
            p1 = p1->next;
        } else {
            p2->next = p;
            p2 = p2->next;
        }
        p = p->next;
    }
    p2->next = NULL;
    p1->next = dummy2->next;
    return dummy1->next;
}

struct ListNode* mergeLists(struct ListNode** lists, int left, int right) {
    if (left == right) {
        return lists[left];
    } else if (left > right) {
        return NULL;
    } else {
        int mid = (left + right) >> 1;
        return mergeTwoLists(mergeLists(lists, left, mid), mergeLists(lists, mid + 1, right));
    }
}


struct ListNode* mergeKLists(struct ListNode** lists, int listsSize){
    return mergeLists(lists, 0, listsSize - 1);
}

struct ListNode* removeNthFromEnd(struct ListNode* head, int n){
    struct ListNode* dummy = (struct ListNode*) malloc(sizeof(struct ListNode));
    dummy->next = head;
    struct ListNode *fast = dummy, *slow = dummy;
    for (int i = 0; i < n; ++i) {
        fast = fast->next;
    }

    while (fast->next) {
        slow = slow->next;
        fast = fast->next;
    }

    slow->next = slow->next->next;
    return dummy->next;
}

struct ListNode* middleNode(struct ListNode* head){
    struct ListNode* slow = head, * fast = head;
    while (fast != NULL && fast->next != NULL) {
        slow = slow->next;
        fast = fast->next->next;
    }
    return slow;
}

struct ListNode *detectCycle(struct ListNode *head) {
    struct ListNode* slow = head, * fast = head;
    while (fast && fast->next) {
        slow = slow->next;
        fast = fast->next->next;
        if (slow == fast) {
            slow = head;
            while (slow != fast) {
                slow = slow->next;
                fast = fast->next;
            }
            return slow;
        }
    }
    return NULL;
}


struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) {
    struct ListNode* p1 = headA, * p2 = headB;
    while (p1 != p2) {
        if (p1) {
            p1 = p1->next;
        } else {
            p1 = headB;
        }

        if (p2) {
            p2 = p2->next;
        } else {
            p2 = headA;
        }
    }

    return p1;
}


struct ListNode* deleteDuplicates(struct ListNode* head){
    struct ListNode* slow = head, * fast = head;
    while (fast) {
        if (slow->val != fast->val) {
            slow = slow->next;
            slow->val = fast->val;
        }
        fast = fast->next;
    }
    if (slow) {
        slow->next = NULL;
    }
    return head;
}


struct ListNode* reverseList(struct ListNode* head) {
    if (head == NULL || head->next == NULL) {
        return head;
    }

    struct ListNode *last = reverseList(head->next);
    head->next->next = head;
    head->next = NULL;
    return last;
}

struct ListNode* successor = NULL;

struct ListNode* reverseN(struct ListNode* head, int n) {
    if (n == 1) {
        successor = head->next;
        return head;
    }
    struct ListNode *last = reverseN(head->next, n - 1);
    head->next->next = head;
    head->next = successor;
    return last;
}

struct ListNode* reverseBetween(struct ListNode* head, int left, int right) {
    if (left == 1) {
        return reverseN(head, right);
    }
    head->next = reverseBetween(head->next, left - 1, right - 1);
    return head;
}

struct ListNode* reverseBetweenK(struct ListNode *start, struct ListNode *end) {
    struct ListNode *prev = NULL, *cur = start, *next;
    while (cur != end) {
        next = cur->next;
        cur->next = prev;
        prev = cur;
        cur = next;
    }
    return prev;
}

struct ListNode* reverseKGroup(struct ListNode* head, int k) {
    if (head == NULL) {
        return head;
    }
    struct ListNode *start = head, *end = start;
    for (int i = 0; i < k; ++i) {
        if (end == NULL)
            return head;
        end = end->next;
    }
    struct ListNode *newStart = reverseBetweenK(start, end);
    start->next = reverseKGroup(end, k);
    return newStart;
}

struct ListNode* left;

bool traverseLinkedList(struct ListNode* right) {
    if (right == NULL) {
        return true;
    }
    bool res = traverseLinkedList(right->next);
    res = res & (left->val == right->val ? true : false);
    left = left->next;
    return res;
}
bool isPalindrome(struct ListNode* head) {
    left = head;
    return traverseLinkedList(head);
}

struct ListNode* rotateRight(struct ListNode* head, int k) {
    if (k == 0 || head == NULL || head->next == NULL)
        return head;
    int n = 1;
    struct ListNode* iter = head;
    while (iter->next) {
        iter = iter->next;
        ++n;
    }
    int rest = n - k % n;
    if (rest == n) {
        return head;
    }
    iter->next = head;
    while (rest--) {
        iter = iter->next;
    }
    struct ListNode* res = iter->next;
    iter->next = NULL;
    return res;
}


int main() {
//    test();
    struct ListNode *list1 = (struct ListNode *) malloc(sizeof(struct ListNode));
    list1->val = 1;
    list1->next = (struct ListNode *) malloc(sizeof(struct ListNode));
    list1->next->val = 2;
    list1->next->next = (struct ListNode *) malloc(sizeof(struct ListNode));
    list1->next->next->val = 4;
    list1->next->next->next = NULL;

    struct ListNode *list2 = (struct ListNode *) malloc(sizeof(struct ListNode));
    list2->val = 1;
    list2->next = (struct ListNode *) malloc(sizeof(struct ListNode));
    list2->next->val = 2;
    list2->next->next = (struct ListNode *) malloc(sizeof(struct ListNode));
    list2->next->next->val = 4;
    list2->next->next->next = NULL;
    mergeTwoLists(list1, list2);
}